package main

import "fmt"

/**
平均时间复杂度和最坏时间复杂度都是O(n^2)
最好情况下是O(n) 空间复杂度O(1)
如果第一轮下来doswap为false，这种情况时间复杂度为O(n)
解析:
3, 1, 5, 4, 1, 7 一共6个数
相邻两数进行比较，设j为当前数索引，初值为0，如果a[j]>a[j+1]，交换两者,然后j+1,反复执行最终求得a[5]为7,j为4
一轮确定一个数，6个数需要5轮比较，n个数需要n-1轮比较
第一轮6个数 5次比较
第二轮5个数 4次比较
...
第五轮2个数 1次比较
可以看到比较次数+轮数=6 即比较次数=len(a)-轮数
比较轮数=i+1，故比较次数=len(a)-(i+1)


*/
//冒泡排序
func bubbleSort(a []int) []int {
	length := len(a)
	for i := 0; i < length-1; i++ {
		doswap := false
		for j := 0; j < length-i-1; j++ {
			if a[j] > a[j+1] {
				a[j], a[j+1] = a[j+1], a[j] //交换两个变量的值go语言支持单行运算
				doswap = true
			}
		}
		if doswap == false {
			return a
		}
	}
	return a
}

func main() {
	fmt.Println(bubbleSort([]int{1, 2, 3, 4}))
}
